home *** CD-ROM | disk | FTP | other *** search
/ Nebula 1 / Nebula One.iso / Mail / EnhanceMail.1.3 / Source / regexp.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-11-05  |  31.0 KB  |  1,319 lines
  1. /*
  2.  * regcomp and regexec -- regsub and regerror are elsewhere
  3.  *
  4.  *    Copyright (c) 1986 by University of Toronto.
  5.  *    Written by Henry Spencer.  Not derived from licensed software.
  6.  *
  7.  *    Permission is granted to anyone to use this software for any
  8.  *    purpose on any computer system, and to redistribute it freely,
  9.  *    subject to the following restrictions:
  10.  *
  11.  *    1. The author is not responsible for the consequences of use of
  12.  *        this software, no matter how awful, even if they arise
  13.  *        from defects in it.
  14.  *
  15.  *    2. The origin of this software must not be misrepresented, either
  16.  *        by explicit claim or by omission.
  17.  *
  18.  *    3. Altered versions must be plainly marked as such, and must not
  19.  *        be misrepresented as being the original software.
  20.  *** THIS IS AN ALTERED VERSION.  It was altered by John Gilmore,
  21.  *** hoptoad!gnu, on 27 Dec 1986, to add \n as an alternative to |
  22.  *** to assist in implementing egrep.
  23.  *** THIS IS AN ALTERED VERSION.  It was altered by John Gilmore,
  24.  *** hoptoad!gnu, on 27 Dec 1986, to add \< and \> for word-matching
  25.  *** as in BSD grep and ex.
  26.  *** THIS IS AN ALTERED VERSION.  It was altered by John Gilmore,
  27.  *** hoptoad!gnu, on 28 Dec 1986, to optimize characters quoted with \.
  28.  *** THIS IS AN ALTERED VERSION.  It was altered by James A. Woods,
  29.  *** ames!jaw, on 19 June 1987, to quash a regcomp() redundancy.
  30.  *
  31.  * Beware that some of this code is subtly aware of the way operator
  32.  * precedence is structured in regular expressions.  Serious changes in
  33.  * regular-expression syntax might require a total rethink.
  34.  */
  35. #include <stdio.h>
  36. #include <ctype.h>
  37. #include "regexp.h"
  38. #include "regmagic.h"
  39. #ifdef __STDC__
  40. #include <string.h>
  41. #include <stdlib.h>
  42. #else  /* __STDC__ */
  43. extern char *strchr();
  44. #endif /* __STDC__ */
  45.  
  46. /*
  47.  * The "internal use only" fields in regexp.h are present to pass info from
  48.  * compile to execute that permits the execute phase to run lots faster on
  49.  * simple cases.  They are:
  50.  *
  51.  * regstart    char that must begin a match; '\0' if none obvious
  52.  * reganch    is the match anchored (at beginning-of-line only)?
  53.  * regmust    string (pointer into program) that match must include, or NULL
  54.  * regmlen    length of regmust string
  55.  *
  56.  * Regstart and reganch permit very fast decisions on suitable starting points
  57.  * for a match, cutting down the work a lot.  Regmust permits fast rejection
  58.  * of lines that cannot possibly match.  The regmust tests are costly enough
  59.  * that regcomp() supplies a regmust only if the r.e. contains something
  60.  * potentially expensive (at present, the only such thing detected is * or +
  61.  * at the start of the r.e., which can involve a lot of backup).  Regmlen is
  62.  * supplied because the test in regexec() needs it and regcomp() is computing
  63.  * it anyway.
  64.  */
  65.  
  66. /*
  67.  * Structure for regexp "program".  This is essentially a linear encoding
  68.  * of a nondeterministic finite-state machine (aka syntax charts or
  69.  * "railroad normal form" in parsing technology).  Each node is an opcode
  70.  * plus a "next" pointer, possibly plus an operand.  "Next" pointers of
  71.  * all nodes except BRANCH implement concatenation; a "next" pointer with
  72.  * a BRANCH on both ends of it is connecting two alternatives.  (Here we
  73.  * have one of the subtle syntax dependencies:  an individual BRANCH (as
  74.  * opposed to a collection of them) is never concatenated with anything
  75.  * because of operator precedence.)  The operand of some types of node is
  76.  * a literal string; for others, it is a node leading into a sub-FSM.  In
  77.  * particular, the operand of a BRANCH node is the first node of the branch.
  78.  * (NB this is *not* a tree structure:  the tail of the branch connects
  79.  * to the thing following the set of BRANCHes.)  The opcodes are:
  80.  */
  81.  
  82. /* definition    number    opnd?    meaning */
  83. #define    END    0    /* no    End of program. */
  84. #define    BOL    1    /* no    Match "" at beginning of line. */
  85. #define    EOL    2    /* no    Match "" at end of line. */
  86. #define    ANY    3    /* no    Match any one character. */
  87. #define    ANYOF    4    /* str    Match any character in this string. */
  88. #define    ANYBUT    5    /* str    Match any character not in this string. */
  89. #define    BRANCH    6    /* node    Match this alternative, or the next... */
  90. #define    BACK    7    /* no    Match "", "next" ptr points backward. */
  91. #define    EXACTLY    8    /* str    Match this string. */
  92. #define    NOTHING    9    /* no    Match empty string. */
  93. #define    STAR    10    /* node    Match this (simple) thing 0 or more times. */
  94. #define    PLUS    11    /* node    Match this (simple) thing 1 or more times. */
  95. #define    WORDA    12    /* no    Match "" at wordchar, where prev is nonword */
  96. #define    WORDZ    13    /* no    Match "" at nonwordchar, where prev is word */
  97. #define    OPEN    20    /* no    Mark this point in input as start of #n. */
  98. /*    OPEN+1 is number 1, etc. */
  99. #define    CLOSE    30    /* no    Analogous to OPEN. */
  100.  
  101. /*
  102.  * Opcode notes:
  103.  *
  104.  * BRANCH    The set of branches constituting a single choice are hooked
  105.  *        together with their "next" pointers, since precedence prevents
  106.  *        anything being concatenated to any individual branch.  The
  107.  *        "next" pointer of the last BRANCH in a choice points to the
  108.  *        thing following the whole choice.  This is also where the
  109.  *        final "next" pointer of each individual branch points; each
  110.  *        branch starts with the operand node of a BRANCH node.
  111.  *
  112.  * BACK        Normal "next" pointers all implicitly point forward; BACK
  113.  *        exists to make loop structures possible.
  114.  *
  115.  * STAR,PLUS    '?', and complex '*' and '+', are implemented as circular
  116.  *        BRANCH structures using BACK.  Simple cases (one character
  117.  *        per match) are implemented with STAR and PLUS for speed
  118.  *        and to minimize recursive plunges.
  119.  *
  120.  * OPEN,CLOSE    ...are numbered at compile time.
  121.  */
  122.  
  123. /*
  124.  * A node is one char of opcode followed by two chars of "next" pointer.
  125.  * "Next" pointers are stored as two 8-bit pieces, high order first.  The
  126.  * value is a positive offset from the opcode of the node containing it.
  127.  * An operand, if any, simply follows the node.  (Note that much of the
  128.  * code generation knows about this implicit relationship.)
  129.  *
  130.  * Using two bytes for the "next" pointer is vast overkill for most things,
  131.  * but allows patterns to get big without disasters.
  132.  */
  133. #define    OP(p)    (*(p))
  134. #define    NEXT(p)    (((*((p)+1)&0377)<<8) + (*((p)+2)&0377))
  135. #define    OPERAND(p)    ((p) + 3)
  136.  
  137. /*
  138.  * See regmagic.h for one further detail of program structure.
  139.  */
  140.  
  141.  
  142. /*
  143.  * Utility definitions.
  144.  */
  145. #ifndef CHARBITS
  146. #define    UCHARAT(p)    ((int)*(unsigned char *)(p))
  147. #else
  148. #define    UCHARAT(p)    ((int)*(p)&CHARBITS)
  149. #endif
  150.  
  151. #define    FAIL(m)    { regerror(m); return(NULL); }
  152. #define    ISMULT(c)    ((c) == '*' || (c) == '+' || (c) == '?')
  153.  
  154. /*
  155.  * Flags to be passed up and down.
  156.  */
  157. #define    HASWIDTH    01    /* Known never to match null string. */
  158. #define    SIMPLE        02    /* Simple enough to be STAR/PLUS operand. */
  159. #define    SPSTART        04    /* Starts with * or +. */
  160. #define    WORST        0    /* Worst case. */
  161.  
  162. /*
  163.  * Global work variables for regcomp().
  164.  */
  165. static const char *regparse;    /* Input-scan pointer. */
  166. static int regnpar;        /* () count. */
  167. static char regdummy;
  168. static char *regcode;        /* Code-emit pointer; ®dummy = don't. */
  169. static long regsize;        /* Code size. */
  170.  
  171. /*
  172.  * Forward declarations for regcomp()'s friends.
  173.  */
  174. #ifndef STATIC
  175. #define    STATIC    static
  176. #endif
  177.  
  178. static char * reg(int paren, int *flagp);
  179. static char * regbranch(int *flagp);
  180. static char * regpiece(int *flagp);
  181. static char *regatom(int *flagp);
  182. static char * regnode(char op);
  183. static void regc(char b);
  184. static void reginsert(char op, char *opnd);
  185. static void regtail(char *p, char *val);
  186. static void regoptail(char *p, char *val);
  187. static int regtry(regexp *prog, const char *string);
  188. static int regmatch(char *prog);
  189. static int regrepeat(char *p);
  190. static char * regnext(char *p);
  191. #ifdef STRCSPN
  192. static int strcspn(char *s1, char *s2);
  193. #endif
  194.  
  195. /*
  196.  - regcomp - compile a regular expression into internal code
  197.  *
  198.  * We can't allocate space until we know how big the compiled form will be,
  199.  * but we can't compile it (and thus know how big it is) until we've got a
  200.  * place to put the code.  So we cheat:  we compile it twice, once with code
  201.  * generation turned off and size counting turned on, and once "for real".
  202.  * This also means that we don't allocate space until we are sure that the
  203.  * thing really will compile successfully, and we never have to move the
  204.  * code and thus invalidate pointers into it.  (Note that it has to be in
  205.  * one piece because free() must be able to free it all.)
  206.  *
  207.  * Beware that the optimization-preparation code in here knows about some
  208.  * of the structure of the compiled regexp.
  209.  */
  210.  
  211. regexp *
  212. regcomp(const char *exp)
  213. {
  214.     regexp *r;
  215.     char *scan;
  216.     char *longest;
  217.     int len;
  218.     int flags;
  219.  
  220.     if (exp == NULL)
  221.     FAIL("NULL argument");
  222.  
  223.     /* First pass: determine size, legality. */
  224.     if (exp[0] == '.' && exp[1] == '*') exp += 2;  /* aid grep */
  225.     regparse = exp;
  226.     regnpar = 1;
  227.     regsize = 0L;
  228.     regcode = ®dummy;
  229.     regc(MAGIC);
  230.     if (reg(0, &flags) == NULL)
  231.     return(NULL);
  232.  
  233.     /* Small enough for pointer-storage convention? */
  234.     if (regsize >= 32767L)        /* Probably could be 65535L. */
  235.     FAIL("regexp too big");
  236.  
  237.     /* Allocate space. */
  238.     r = (regexp *)malloc(sizeof(regexp) + (unsigned)regsize);
  239.     if (r == NULL)
  240.     FAIL("out of space");
  241.  
  242.     /* Second pass: emit code. */
  243.     regparse = exp;
  244.     regnpar = 1;
  245.     regcode = r->program;
  246.     regc(MAGIC);
  247.     if (reg(0, &flags) == NULL)
  248.     return(NULL);
  249.  
  250.     /* Dig out information for optimizations. */
  251.     r->regstart = '\0';    /* Worst-case defaults. */
  252.     r->reganch = 0;
  253.     r->regmust = NULL;
  254.     r->regmlen = 0;
  255.     scan = r->program+1;            /* First BRANCH. */
  256.     if (OP(regnext(scan)) == END) {        /* Only one top-level choice. */
  257.     scan = OPERAND(scan);
  258.  
  259.     /* Starting-point info. */
  260.     if (OP(scan) == EXACTLY)
  261.         r->regstart = *OPERAND(scan);
  262.     else if (OP(scan) == BOL)
  263.         r->reganch++;
  264.  
  265.     /*
  266.      * If there's something expensive in the r.e., find the
  267.      * longest literal string that must appear and make it the
  268.      * regmust.  Resolve ties in favor of later strings, since
  269.      * the regstart check works with the beginning of the r.e.
  270.      * and avoiding duplication strengthens checking.  Not a
  271.      * strong reason, but sufficient in the absence of others.
  272.      */
  273.     if (flags&SPSTART) {
  274.         longest = NULL;
  275.         len = 0;
  276.         for (; scan != NULL; scan = regnext(scan))
  277.         if (OP(scan) == EXACTLY && strlen(OPERAND(scan)) >= len) {
  278.             longest = OPERAND(scan);
  279.             len = strlen(OPERAND(scan));
  280.         }
  281.         r->regmust = longest;
  282.         r->regmlen = len;
  283.     }
  284.     }
  285.  
  286.     return(r);
  287. }
  288.  
  289. /* 
  290.    regtest() -- returns 0 if the regex is fine, or an error string if it's 
  291.    invalid.
  292.    
  293.  */
  294.  
  295. char *
  296. regtest(const char *exp)
  297. {
  298.     void * val = regcomp(exp);
  299.     if (val) {
  300.     free(val);
  301.     return 0;
  302.     } else {
  303.     return regerrval;
  304.     }
  305. }
  306.  
  307. /*
  308.  - reg - regular expression, i.e. main body or parenthesized thing
  309.  *
  310.  * Caller must absorb opening parenthesis.
  311.  *
  312.  * Combining parenthesis handling with the base level of regular expression
  313.  * is a trifle forced, but the need to tie the tails of the branches to what
  314.  * follows makes it hard to avoid.
  315.  */
  316. static char *
  317. reg(int paren, int *flagp)
  318. {
  319.     char *ret;
  320.     char *br;
  321.     char *ender;
  322.     int parno = 0;
  323.     int flags;
  324.  
  325.     *flagp = HASWIDTH;    /* Tentatively. */
  326.  
  327.     /* Make an OPEN node, if parenthesized. */
  328.     if (paren) {
  329.     if (regnpar >= NSUBEXP)
  330.         FAIL("too many ()");
  331.     parno = regnpar;
  332.     regnpar++;
  333.     ret = regnode(OPEN+parno);
  334.     } else
  335.     ret = NULL;
  336.  
  337.     /* Pick up the branches, linking them together. */
  338.     br = regbranch(&flags);
  339.     if (br == NULL)
  340.     return(NULL);
  341.     if (ret != NULL)
  342.     regtail(ret, br);    /* OPEN -> first. */
  343.     else
  344.     ret = br;
  345.     if (!(flags&HASWIDTH))
  346.     *flagp &= ~HASWIDTH;
  347.     *flagp |= flags&SPSTART;
  348.     while (*regparse == '|' || *regparse == '\n') {
  349.     regparse++;
  350.     br = regbranch(&flags);
  351.     if (br == NULL)
  352.         return(NULL);
  353.     regtail(ret, br);    /* BRANCH -> BRANCH. */
  354.     if (!(flags&HASWIDTH))
  355.         *flagp &= ~HASWIDTH;
  356.     *flagp |= flags&SPSTART;
  357.     }
  358.  
  359.     /* Make a closing node, and hook it on the end. */
  360.     ender = regnode((paren) ? CLOSE+parno : END);    
  361.     regtail(ret, ender);
  362.  
  363.     /* Hook the tails of the branches to the closing node. */
  364.     for (br = ret; br != NULL; br = regnext(br))
  365.     regoptail(br, ender);
  366.  
  367.     /* Check for proper termination. */
  368.     if (paren && *regparse++ != ')') {
  369.     FAIL("unmatched ()");
  370.     } else if (!paren && *regparse != '\0') {
  371.     if (*regparse == ')') {
  372.         FAIL("unmatched ()");
  373.     } else
  374.         FAIL("junk on end");    /* "Can't happen". */
  375.     /* NOTREACHED */
  376.     }
  377.  
  378.     return(ret);
  379. }
  380.  
  381. /*
  382.  - regbranch - one alternative of an | operator
  383.  *
  384.  * Implements the concatenation operator.
  385.  */
  386. static char *
  387. regbranch(int *flagp)
  388. {
  389.     char *ret;
  390.     char *chain;
  391.     char *latest;
  392.     int flags;
  393.  
  394.     *flagp = WORST;        /* Tentatively. */
  395.  
  396.     ret = regnode(BRANCH);
  397.     chain = NULL;
  398.     while (*regparse != '\0' && *regparse != ')' &&
  399.        *regparse != '\n' && *regparse != '|') {
  400.     latest = regpiece(&flags);
  401.     if (latest == NULL)
  402.         return(NULL);
  403.     *flagp |= flags&HASWIDTH;
  404.     if (chain == NULL)    /* First piece. */
  405.         *flagp |= flags&SPSTART;
  406.     else
  407.         regtail(chain, latest);
  408.     chain = latest;
  409.     }
  410.     if (chain == NULL)    /* Loop ran zero times. */
  411.     (void) regnode(NOTHING);
  412.  
  413.     return(ret);
  414. }
  415.  
  416. /*
  417.  - regpiece - something followed by possible [*+?]
  418.  *
  419.  * Note that the branching code sequences used for ? and the general cases
  420.  * of * and + are somewhat optimized:  they use the same NOTHING node as
  421.  * both the endmarker for their branch list and the body of the last branch.
  422.  * It might seem that this node could be dispensed with entirely, but the
  423.  * endmarker role is not redundant.
  424.  */
  425. static char *
  426. regpiece(int *flagp)
  427. {
  428.     char *ret;
  429.     char op;
  430.     char *next;
  431.     int flags;
  432.  
  433.     ret = regatom(&flags);
  434.     if (ret == NULL)
  435.     return(NULL);
  436.  
  437.     op = *regparse;
  438.     if (!ISMULT(op)) {
  439.     *flagp = flags;
  440.     return(ret);
  441.     }
  442.  
  443.     if (!(flags&HASWIDTH) && op != '?')
  444.     FAIL("*+ operand could be empty");
  445.     *flagp = (op != '+') ? (WORST|SPSTART) : (WORST|HASWIDTH);
  446.  
  447.     if (op == '*' && (flags&SIMPLE))
  448.     reginsert(STAR, ret);
  449.     else if (op == '*') {
  450.     /* Emit x* as (x&|), where & means "self". */
  451.     reginsert(BRANCH, ret);            /* Either x */
  452.     regoptail(ret, regnode(BACK));        /* and loop */
  453.     regoptail(ret, ret);            /* back */
  454.     regtail(ret, regnode(BRANCH));        /* or */
  455.     regtail(ret, regnode(NOTHING));        /* null. */
  456.     } else if (op == '+' && (flags&SIMPLE))
  457.     reginsert(PLUS, ret);
  458.     else if (op == '+') {
  459.     /* Emit x+ as x(&|), where & means "self". */
  460.     next = regnode(BRANCH);            /* Either */
  461.     regtail(ret, next);
  462.     regtail(regnode(BACK), ret);        /* loop back */
  463.     regtail(next, regnode(BRANCH));        /* or */
  464.     regtail(ret, regnode(NOTHING));        /* null. */
  465.     } else if (op == '?') {
  466.     /* Emit x? as (x|) */
  467.     reginsert(BRANCH, ret);            /* Either x */
  468.     regtail(ret, regnode(BRANCH));        /* or */
  469.     next = regnode(NOTHING);        /* null. */
  470.     regtail(ret, next);
  471.     regoptail(ret, next);
  472.     }
  473.     regparse++;
  474.     if (ISMULT(*regparse))
  475.     FAIL("nested *?+");
  476.  
  477.     return(ret);
  478. }
  479.  
  480. /*
  481.  - regatom - the lowest level
  482.  *
  483.  * Optimization:  gobbles an entire sequence of ordinary characters so that
  484.  * it can turn them into a single node, which is smaller to store and
  485.  * faster to run.  Backslashed characters are exceptions, each becoming a
  486.  * separate node; the code is simpler that way and it's not worth fixing.
  487.  */
  488. static char *
  489. regatom(int *flagp)
  490. {
  491.     char *ret;
  492.     int flags;
  493.  
  494.     *flagp = WORST;        /* Tentatively. */
  495.  
  496.     switch (*regparse++) {
  497.     /* FIXME: these chars only have meaning at beg/end of pat? */
  498.     case '^':
  499.     ret = regnode(BOL);
  500.     break;
  501.     case '$':
  502.     ret = regnode(EOL);
  503.     break;
  504.     case '.':
  505.     ret = regnode(ANY);
  506.     *flagp |= HASWIDTH|SIMPLE;
  507.     break;
  508.     case '[': {
  509.     int class;
  510.     int classend;
  511.  
  512.     if (*regparse == '^') {    /* Complement of range. */
  513.         ret = regnode(ANYBUT);
  514.         regparse++;
  515.     } else
  516.         ret = regnode(ANYOF);
  517.     if (*regparse == ']' || *regparse == '-')
  518.         regc(*regparse++);
  519.     while (*regparse != '\0' && *regparse != ']') {
  520.         if (*regparse == '-') {
  521.         regparse++;
  522.         if (*regparse == ']' || *regparse == '\0')
  523.             regc('-');
  524.         else {
  525.             class = UCHARAT(regparse-2)+1;
  526.             classend = UCHARAT(regparse);
  527.             if (class > classend+1)
  528.             FAIL("invalid [] range");
  529.             for (; class <= classend; class++)
  530.             regc(class);
  531.             regparse++;
  532.         }
  533.         } else
  534.         regc(*regparse++);
  535.     }
  536.     regc('\0');
  537.     if (*regparse != ']')
  538.         FAIL("unmatched []");
  539.     regparse++;
  540.     *flagp |= HASWIDTH|SIMPLE;
  541.     }
  542.     break;
  543.     case '(':
  544.     ret = reg(1, &flags);
  545.     if (ret == NULL)
  546.         return(NULL);
  547.     *flagp |= flags&(HASWIDTH|SPSTART);
  548.     break;
  549.     case '\0':
  550.     case '|':
  551.     case '\n':
  552.     case ')':
  553.     FAIL("internal urp");    /* Supposed to be caught earlier. */
  554.     break;
  555.     case '?':
  556.     case '+':
  557.     case '*':
  558.     FAIL("?+* follows nothing");
  559.     break;
  560.     case '\\':
  561.     switch (*regparse++) {
  562.     case '\0':
  563.         FAIL("trailing \\");
  564.         break;
  565.     case '<':
  566.         ret = regnode(WORDA);
  567.         break;
  568.     case '>':
  569.         ret = regnode(WORDZ);
  570.         break;
  571.         /* FIXME: Someday handle \1, \2, ... */
  572.     default:
  573.         /* Handle general quoted chars in exact-match routine */
  574.         goto de_fault;
  575.     }
  576.         break;
  577. de_fault:
  578.     default:
  579.     /*
  580.      * Encode a string of characters to be matched exactly.
  581.      *
  582.      * This is a bit tricky due to quoted chars and due to
  583.      * '*', '+', and '?' taking the SINGLE char previous
  584.      * as their operand.
  585.      *
  586.      * On entry, the char at regparse[-1] is going to go
  587.      * into the string, no matter what it is.  (It could be
  588.      * following a \ if we are entered from the '\' case.)
  589.      * 
  590.      * Basic idea is to pick up a good char in  ch  and
  591.      * examine the next char.  If it's *+? then we twiddle.
  592.      * If it's \ then we frozzle.  If it's other magic char
  593.      * we push  ch  and terminate the string.  If none of the
  594.      * above, we push  ch  on the string and go around again.
  595.      *
  596.      *  regprev  is used to remember where "the current char"
  597.      * starts in the string, if due to a *+? we need to back
  598.      * up and put the current char in a separate, 1-char, string.
  599.      * When  regprev  is NULL,  ch  is the only char in the
  600.      * string; this is used in *+? handling, and in setting
  601.      * flags |= SIMPLE at the end.
  602.      */
  603.     {
  604.     const char *regprev;
  605.     char ch;
  606.  
  607.     regparse--;            /* Look at cur char */
  608.     ret = regnode(EXACTLY);
  609.     for ( regprev = 0 ; ; ) {
  610.         ch = *regparse++;    /* Get current char */
  611.         switch (*regparse) {    /* look at next one */
  612.  
  613.         default:
  614.         regc(ch);    /* Add cur to string */
  615.         break;
  616.  
  617.         case '.': case '[': case '(':
  618.         case ')': case '|': case '\n':
  619.         case '$': case '^':
  620.         case '\0':
  621.         /* FIXME, $ and ^ should not always be magic */
  622.     magic:
  623.         regc(ch);    /* dump cur char */
  624.         goto done;    /* and we are done */
  625.  
  626.         case '?': case '+': case '*':
  627.         if (!regprev)     /* If just ch in str, */
  628.             goto magic;    /* use it */
  629.                     /* End mult-char string one early */
  630.         regparse = regprev; /* Back up parse */
  631.         goto done;
  632.  
  633.         case '\\':
  634.         regc(ch);    /* Cur char OK */
  635.         switch (regparse[1]){ /* Look after \ */
  636.         case '\0':
  637.         case '<':
  638.         case '>':
  639.                     /* FIXME: Someday handle \1, \2, ... */
  640.             goto done; /* Not quoted */
  641.         default:
  642.                     /* Backup point is \, scan                             * point is after it. */
  643.             regprev = regparse;
  644.             regparse++; 
  645.             continue;    /* NOT break; */
  646.         }
  647.         }
  648.         regprev = regparse;    /* Set backup point */
  649.     }
  650. done:
  651.     regc('\0');
  652.     *flagp |= HASWIDTH;
  653.     if (!regprev)        /* One char? */
  654.         *flagp |= SIMPLE;
  655.     }
  656.             break;
  657.     }
  658.  
  659.     return(ret);
  660. }
  661.  
  662. /*
  663.  - regnode - emit a node
  664.  */
  665. static char *            /* Location. */
  666. regnode(char op)
  667. {
  668.     char *ret;
  669.     char *ptr;
  670.  
  671.     ret = regcode;
  672.     if (ret == ®dummy) {
  673.     regsize += 3;
  674.     return(ret);
  675.     }
  676.  
  677.     ptr = ret;
  678.     *ptr++ = op;
  679.     *ptr++ = '\0';        /* Null "next" pointer. */
  680.     *ptr++ = '\0';
  681.     regcode = ptr;
  682.  
  683.     return(ret);
  684. }
  685.  
  686. /*
  687.  - regc - emit (if appropriate) a byte of code
  688.  */
  689. static void
  690. regc(char b)
  691. {
  692.     if (regcode != ®dummy)
  693.     *regcode++ = b;
  694.     else
  695.     regsize++;
  696. }
  697.  
  698. /*
  699.  - reginsert - insert an operator in front of already-emitted operand
  700.  *
  701.  * Means relocating the operand.
  702.  */
  703. static void
  704. reginsert(char op, char *opnd)
  705. {
  706.     char *src;
  707.     char *dst;
  708.     char *place;
  709.  
  710.     if (regcode == ®dummy) {
  711.     regsize += 3;
  712.     return;
  713.     }
  714.  
  715.     src = regcode;
  716.     regcode += 3;
  717.     dst = regcode;
  718.     while (src > opnd)
  719.     *--dst = *--src;
  720.  
  721.     place = opnd;        /* Op node, where operand used to be. */
  722.     *place++ = op;
  723.     *place++ = '\0';
  724.     *place++ = '\0';
  725. }
  726.  
  727. /*
  728.  - regtail - set the next-pointer at the end of a node chain
  729.  */
  730. static void
  731. regtail(char *p, char *val)
  732. {
  733.     char *scan;
  734.     char *temp;
  735.     int offset;
  736.  
  737.     if (p == ®dummy)
  738.     return;
  739.  
  740.     /* Find last node. */
  741.     scan = p;
  742.     for (;;) {
  743.     temp = regnext(scan);
  744.     if (temp == NULL)
  745.         break;
  746.     scan = temp;
  747.     }
  748.  
  749.     if (OP(scan) == BACK)
  750.     offset = scan - val;
  751.     else
  752.     offset = val - scan;
  753.     *(scan+1) = (offset>>8)&0377;
  754.     *(scan+2) = offset&0377;
  755. }
  756.  
  757. /*
  758.  - regoptail - regtail on operand of first argument; nop if operandless
  759.  */
  760. static void
  761. regoptail(char *p, char *val)
  762. {
  763.     /* "Operandless" and "op != BRANCH" are synonymous in practice. */
  764.     if (p == NULL || p == ®dummy || OP(p) != BRANCH)
  765.     return;
  766.     regtail(OPERAND(p), val);
  767. }
  768.  
  769. /*
  770.  * regexec and friends
  771.  */
  772.  
  773. /*
  774.  * Global work variables for regexec().
  775.  */
  776. static const char *reginput;    /* String-input pointer. */
  777. static const char *regbol;    /* Beginning of input, for ^ check. */
  778. static const char **regstartp;    /* Pointer to startp array. */
  779. static const char **regendp;    /* Ditto for endp. */
  780.  
  781. /*
  782.  * Forwards.
  783.  */
  784. STATIC int regtry();
  785. STATIC int regmatch();
  786. STATIC int regrepeat();
  787.  
  788. #ifdef DEBUG
  789. int regnarrate = 0;
  790. void regdump();
  791. STATIC char *regprop();
  792. #endif
  793.  
  794. /*
  795.  - regexec - match a regexp against a string
  796.  */
  797. int
  798. regexec(regexp *prog, const char *string)
  799. {
  800.     const char *s;
  801.     /* Be paranoid... */
  802.     if (prog == NULL || string == NULL) {
  803.     regerror("NULL parameter");
  804.     return(0);
  805.     }
  806.  
  807.     /* Check validity of program. */
  808.     if (UCHARAT(prog->program) != MAGIC) {
  809.     regerror("corrupted program");
  810.     return(0);
  811.     }
  812.  
  813.     /* If there is a "must appear" string, look for it. */
  814.     if (prog->regmust != NULL) {
  815.     s = string;
  816.     while ((s = strchr(s, prog->regmust[0])) != NULL) {
  817.         if (strncmp(s, prog->regmust, prog->regmlen) == 0)
  818.         break;    /* Found it. */
  819.         s++;
  820.     }
  821.     if (s == NULL)    /* Not present. */
  822.         return(0);
  823.     }
  824.  
  825.     /* Mark beginning of line for ^ . */
  826.     regbol = string;
  827.  
  828.     /* Simplest case:  anchored match need be tried only once. */
  829.     if (prog->reganch)
  830.     return(regtry(prog, string));
  831.  
  832.     /* Messy cases:  unanchored match. */
  833.     s = string;
  834.     if (prog->regstart != '\0')
  835.     /* We know what char it must start with. */
  836.     while ((s = strchr(s, prog->regstart)) != NULL) {
  837.         if (regtry(prog, s))
  838.         return(1);
  839.         s++;
  840.     }
  841.     else
  842.     /* We don't -- general case. */
  843.     do {
  844.         if (regtry(prog, s))
  845.         return(1);
  846.     } while (*s++ != '\0');
  847.  
  848.     /* Failure. */
  849.     return(0);
  850. }
  851.  
  852. /*
  853.  - regtry - try match at specific point
  854.  */
  855. static int            /* 0 failure, 1 success */
  856. regtry(regexp *prog, const char *string)
  857. {
  858.     int i;
  859.     char **sp;
  860.     char **ep;
  861.  
  862.     reginput = string;
  863.     regstartp = prog->startp;
  864.     regendp = prog->endp;
  865.  
  866.     sp = prog->startp;
  867.     ep = prog->endp;
  868.     for (i = NSUBEXP; i > 0; i--) {
  869.     *sp++ = NULL;
  870.     *ep++ = NULL;
  871.     }
  872.     if (regmatch(prog->program + 1)) {
  873.     prog->startp[0] = string;
  874.     prog->endp[0] = reginput;
  875.     return(1);
  876.     } else
  877.     return(0);
  878. }
  879.  
  880. /*
  881.  - regmatch - main matching routine
  882.  *
  883.  * Conceptually the strategy is simple:  check to see whether the current
  884.  * node matches, call self recursively to see whether the rest matches,
  885.  * and then act accordingly.  In practice we make some effort to avoid
  886.  * recursion, in particular by going through "ordinary" nodes (that don't
  887.  * need to know whether the rest of the match failed) by a loop instead of
  888.  * by recursion.
  889.  */
  890. static int            /* 0 failure, 1 success */
  891. regmatch(char *prog)
  892. {
  893.     char *scan;    /* Current node. */
  894.     char *next;        /* Next node. */
  895.     extern char *strchr();
  896.  
  897.     scan = prog;
  898. #ifdef DEBUG
  899.     if (scan != NULL && regnarrate)
  900.     fprintf(stderr, "%s(\n", regprop(scan));
  901. #endif
  902.     while (scan != NULL) {
  903. #ifdef DEBUG
  904.     if (regnarrate)
  905.         fprintf(stderr, "%s...\n", regprop(scan));
  906. #endif
  907.     next = regnext(scan);
  908.  
  909.     switch (OP(scan)) {
  910.     case BOL:
  911.         if (reginput != regbol)
  912.         return(0);
  913.         break;
  914.     case EOL:
  915.         if (*reginput != '\0')
  916.         return(0);
  917.         break;
  918.     case WORDA:
  919.         /* Must be looking at a letter, digit, or _ */
  920.         if ((!isalnum(*reginput)) && *reginput != '_')
  921.         return(0);
  922.         /* Prev must be BOL or nonword */
  923.         if (reginput > regbol &&
  924.         (isalnum(reginput[-1]) || reginput[-1] == '_'))
  925.         return(0);
  926.         break;
  927.     case WORDZ:
  928.         /* Must be looking at non letter, digit, or _ */
  929.         if (isalnum(*reginput) || *reginput == '_')
  930.         return(0);
  931.         /* We don't care what the previous char was */
  932.         break;
  933.     case ANY:
  934.         if (*reginput == '\0')
  935.         return(0);
  936.         reginput++;
  937.         break;
  938.     case EXACTLY: {
  939.         int len;
  940.         char *opnd;
  941.  
  942.         opnd = OPERAND(scan);
  943.         /* Inline the first character, for speed. */
  944.         if (*opnd != *reginput)
  945.         return(0);
  946.         len = strlen(opnd);
  947.         if (len > 1 && strncmp(opnd, reginput, len) != 0)
  948.         return(0);
  949.         reginput += len;
  950.     }
  951.         break;
  952.     case ANYOF:
  953.         if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) == NULL)
  954.         return(0);
  955.         reginput++;
  956.         break;
  957.     case ANYBUT:
  958.         if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) != NULL)
  959.         return(0);
  960.         reginput++;
  961.         break;
  962.     case NOTHING:
  963.         break;
  964.     case BACK:
  965.         break;
  966.     case OPEN+1:
  967.     case OPEN+2:
  968.     case OPEN+3:
  969.     case OPEN+4:
  970.     case OPEN+5:
  971.     case OPEN+6:
  972.     case OPEN+7:
  973.     case OPEN+8:
  974.     case OPEN+9: {
  975.         int no;
  976.         const char *save;
  977.  
  978.         no = OP(scan) - OPEN;
  979.         save = reginput;
  980.  
  981.         if (regmatch(next)) {
  982.                     /*
  983.                      * Don't set startp if some later
  984.                      * invocation of the same parentheses
  985.                      * already has.
  986.                      */
  987.         if (regstartp[no] == NULL)
  988.             regstartp[no] = save;
  989.         return(1);
  990.         } else
  991.         return(0);
  992.     }
  993.         break;
  994.     case CLOSE+1:
  995.     case CLOSE+2:
  996.     case CLOSE+3:
  997.     case CLOSE+4:
  998.     case CLOSE+5:
  999.     case CLOSE+6:
  1000.     case CLOSE+7:
  1001.     case CLOSE+8:
  1002.     case CLOSE+9: {
  1003.         int no;
  1004.         const char *save;
  1005.  
  1006.         no = OP(scan) - CLOSE;
  1007.         save = reginput;
  1008.  
  1009.         if (regmatch(next)) {
  1010.                     /*
  1011.                      * Don't set endp if some later
  1012.                      * invocation of the same parentheses
  1013.                      * already has.
  1014.                      */
  1015.         if (regendp[no] == NULL)
  1016.             regendp[no] = save;
  1017.         return(1);
  1018.         } else
  1019.         return(0);
  1020.     }
  1021.         break;
  1022.     case BRANCH: {
  1023.         const char *save;
  1024.  
  1025.         if (OP(next) != BRANCH)        /* No choice. */
  1026.         next = OPERAND(scan);    /* Avoid recursion. */
  1027.         else {
  1028.         do {
  1029.             save = reginput;
  1030.             if (regmatch(OPERAND(scan)))
  1031.             return(1);
  1032.             reginput = save;
  1033.             scan = regnext(scan);
  1034.         } while (scan != NULL && OP(scan) == BRANCH);
  1035.         return(0);
  1036.                     /* NOTREACHED */
  1037.         }
  1038.     }
  1039.         break;
  1040.     case STAR:
  1041.     case PLUS: {
  1042.         char nextch;
  1043.         int no;
  1044.         const char *save;
  1045.         int min;
  1046.  
  1047.         /*
  1048.          * Lookahead to avoid useless match attempts
  1049.          * when we know what character comes next.
  1050.          */
  1051.         nextch = '\0';
  1052.         if (OP(next) == EXACTLY)
  1053.         nextch = *OPERAND(next);
  1054.         min = (OP(scan) == STAR) ? 0 : 1;
  1055.         save = reginput;
  1056.         no = regrepeat(OPERAND(scan));
  1057.         while (no >= min) {
  1058.                     /* If it could work, try it. */
  1059.         if (nextch == '\0' || *reginput == nextch)
  1060.             if (regmatch(next))
  1061.             return(1);
  1062.                     /* Couldn't or didn't -- back up. */
  1063.         no--;
  1064.         reginput = save + no;
  1065.         }
  1066.         return(0);
  1067.     }
  1068.         break;
  1069.     case END:
  1070.         return(1);    /* Success! */
  1071.         break;
  1072.     default:
  1073.         regerror("memory corruption");
  1074.         return(0);
  1075.         break;
  1076.     }
  1077.  
  1078.     scan = next;
  1079.     }
  1080.  
  1081.     /*
  1082.      * We get here only if there's trouble -- normally "case END" is
  1083.      * the terminating point.
  1084.      */
  1085.     regerror("corrupted pointers");
  1086.     return(0);
  1087. }
  1088.  
  1089. /*
  1090.  - regrepeat - repeatedly match something simple, report how many
  1091.  */
  1092. static int
  1093. regrepeat(char *p)
  1094. {
  1095.     int count = 0;
  1096.     const char *scan;
  1097.     char *opnd;
  1098.  
  1099.     scan = reginput;
  1100.     opnd = OPERAND(p);
  1101.     switch (OP(p)) {
  1102.     case ANY:
  1103.     count = strlen(scan);
  1104.     scan += count;
  1105.     break;
  1106.     case EXACTLY:
  1107.     while (*opnd == *scan) {
  1108.         count++;
  1109.         scan++;
  1110.     }
  1111.     break;
  1112.     case ANYOF:
  1113.     while (*scan != '\0' && strchr(opnd, *scan) != NULL) {
  1114.         count++;
  1115.         scan++;
  1116.     }
  1117.     break;
  1118.     case ANYBUT:
  1119.     while (*scan != '\0' && strchr(opnd, *scan) == NULL) {
  1120.         count++;
  1121.         scan++;
  1122.     }
  1123.     break;
  1124.     default:        /* Oh dear.  Called inappropriately. */
  1125.     regerror("internal foulup");
  1126.     count = 0;    /* Best compromise. */
  1127.     break;
  1128.     }
  1129.     reginput = scan;
  1130.  
  1131.     return(count);
  1132. }
  1133.  
  1134. /*
  1135.  - regnext - dig the "next" pointer out of a node
  1136.  */
  1137. static char *
  1138. regnext(char *p)
  1139. {
  1140.     int offset;
  1141.  
  1142.     if (p == ®dummy)
  1143.     return(NULL);
  1144.  
  1145.     offset = NEXT(p);
  1146.     if (offset == 0)
  1147.     return(NULL);
  1148.  
  1149.     if (OP(p) == BACK)
  1150.     return(p-offset);
  1151.     else
  1152.     return(p+offset);
  1153. }
  1154.  
  1155. #ifdef DEBUG
  1156.  
  1157. STATIC char *regprop();
  1158.  
  1159. /*
  1160.  - regdump - dump a regexp onto stdout in vaguely comprehensible form
  1161.  */
  1162. void
  1163. regdump(regexp *r)
  1164. {
  1165.     char *s;
  1166.     char op = EXACTLY;    /* Arbitrary non-END op. */
  1167.     char *next;
  1168.     extern char *strchr();
  1169.  
  1170.  
  1171.     s = r->program + 1;
  1172.     while (op != END) {    /* While that wasn't END last time... */
  1173.     op = OP(s);
  1174.     printf("%2d%s", s-r->program, regprop(s));    /* Where, what. */
  1175.     next = regnext(s);
  1176.     if (next == NULL)        /* Next ptr. */
  1177.         printf("(0)");
  1178.     else 
  1179.         printf("(%d)", (s-r->program)+(next-s));
  1180.     s += 3;
  1181.     if (op == ANYOF || op == ANYBUT || op == EXACTLY) {
  1182.         /* Literal string, where present. */
  1183.         while (*s != '\0') {
  1184.         putchar(*s);
  1185.         s++;
  1186.         }
  1187.         s++;
  1188.     }
  1189.     putchar('\n');
  1190.     }
  1191.  
  1192.     /* Header fields of interest. */
  1193.     if (r->regstart != '\0')
  1194.     printf("start `%c' ", r->regstart);
  1195.     if (r->reganch)
  1196.     printf("anchored ");
  1197.     if (r->regmust != NULL)
  1198.     printf("must have \"%s\"", r->regmust);
  1199.     printf("\n");
  1200. }
  1201.  
  1202. /*
  1203.  - regprop - printable representation of opcode
  1204.  */
  1205. static char *
  1206. regprop(char *op)
  1207. {
  1208.     char *p;
  1209.     static char buf[50];
  1210.  
  1211.     (void) strcpy(buf, ":");
  1212.  
  1213.     switch (OP(op)) {
  1214.     case BOL:
  1215.     p = "BOL";
  1216.     break;
  1217.     case EOL:
  1218.     p = "EOL";
  1219.     break;
  1220.     case ANY:
  1221.     p = "ANY";
  1222.     break;
  1223.     case ANYOF:
  1224.     p = "ANYOF";
  1225.     break;
  1226.     case ANYBUT:
  1227.     p = "ANYBUT";
  1228.     break;
  1229.     case BRANCH:
  1230.     p = "BRANCH";
  1231.     break;
  1232.     case EXACTLY:
  1233.     p = "EXACTLY";
  1234.     break;
  1235.     case NOTHING:
  1236.     p = "NOTHING";
  1237.     break;
  1238.     case BACK:
  1239.     p = "BACK";
  1240.     break;
  1241.     case END:
  1242.     p = "END";
  1243.     break;
  1244.     case OPEN+1:
  1245.     case OPEN+2:
  1246.     case OPEN+3:
  1247.     case OPEN+4:
  1248.     case OPEN+5:
  1249.     case OPEN+6:
  1250.     case OPEN+7:
  1251.     case OPEN+8:
  1252.     case OPEN+9:
  1253.     sprintf(buf+strlen(buf), "OPEN%d", OP(op)-OPEN);
  1254.     p = NULL;
  1255.     break;
  1256.     case CLOSE+1:
  1257.     case CLOSE+2:
  1258.     case CLOSE+3:
  1259.     case CLOSE+4:
  1260.     case CLOSE+5:
  1261.     case CLOSE+6:
  1262.     case CLOSE+7:
  1263.     case CLOSE+8:
  1264.     case CLOSE+9:
  1265.     sprintf(buf+strlen(buf), "CLOSE%d", OP(op)-CLOSE);
  1266.     p = NULL;
  1267.     break;
  1268.     case STAR:
  1269.     p = "STAR";
  1270.     break;
  1271.     case PLUS:
  1272.     p = "PLUS";
  1273.     break;
  1274.     case WORDA:
  1275.     p = "WORDA";
  1276.     break;
  1277.     case WORDZ:
  1278.     p = "WORDZ";
  1279.     break;
  1280.     default:
  1281.     regerror("corrupted opcode");
  1282.     break;
  1283.     }
  1284.     if (p != NULL)
  1285.     (void) strcat(buf, p);
  1286.     return(buf);
  1287. }
  1288. #endif
  1289.  
  1290. /*
  1291.  * The following is provided for those people who do not have strcspn() in
  1292.  * their C libraries.  They should get off their butts and do something
  1293.  * about it; at least one public-domain implementation of those (highly
  1294.  * useful) string routines has been published on Usenet.
  1295.  */
  1296. #ifdef STRCSPN
  1297. /*
  1298.  * strcspn - find length of initial segment of s1 consisting entirely
  1299.  * of characters not from s2
  1300.  */
  1301.  
  1302. static int
  1303. strcspn(char *s1, char *s2)
  1304. {
  1305.     char *scan1;
  1306.     char *scan2;
  1307.     int count;
  1308.  
  1309.     count = 0;
  1310.     for (scan1 = s1; *scan1 != '\0'; scan1++) {
  1311.     for (scan2 = s2; *scan2 != '\0';)    /* ++ moved down. */
  1312.         if (*scan1 == *scan2++)
  1313.         return(count);
  1314.     count++;
  1315.     }
  1316.     return(count);
  1317. }
  1318. #endif
  1319.